#ifndef TESTREACHABILITY_H_INCLUDED
#define TESTREACHABILITY_H_INCLUDED

#include "DGraph.h"
#include "DGraphUtil.h"
#include "headers.h"
#include <set>
#include<hash_map>
//
//struct Hash_Vertex {
//	size_t operator()(const Vertex& v) const {
//
//
//	}
//};

typedef struct {
	int _hop_start, _hop_end;
	int _hop_pren;
	double _density;
} GridHop;

typedef struct {
	int _beg, _end;
} Interval;

typedef hash_set<int> SuccList, PredList;
typedef set<int> InLabel, OutLabel;
typedef struct {
	InLabel _Lin;
	OutLabel _Lout;
} GridHopLabel;


struct HopComp {
	bool operator() (const GridHop& b1, const GridHop& b2) const {
		if ((b1._density<b2._density)||(b1._density==b2._density&&b1._hop_pren>b2._hop_pren))
			return true;
		return false;
	}
};

typedef priority_queue<GridHop, vector<GridHop>, HopComp> HOPQUEUE;


class TestReachability {
private:
	DGraph graph;

	int left;


	//    hash_map<int, int> vertices_chain;
	/*
	 DTree tree;
	 NTEList NTE;
	 LNTEList longNTE;
	 SNTEList shortNTE;
	 */
	//           src trg reachale?
	map<pair<int, int> , bool> _tcm; // test reachability

	// grid-hop labels
	vector<GridHopLabel> _labels;

	VertexList vs;
	VertexList vs2;

	//test
public:
//	long equalEndpoints;
//	long totalCheckHops;
	int contoursize;
	struct Node* root;
	//    vector<int*> result;

public:
	TestReachability();
	TestReachability(DGraph& g);

private:
	map<int, hash_set<int> > contour;
	map<int, hash_set<int> > gsucc;
	map<int, hash_set<int> > upred;
	//int label_dfs2(int vid, int& count, vector<bool>& visited);
	void label_dfs2(DTree& tree, SNTEList& shortNTE, int vid, int& count,
			vector<bool>& visited);
	void index();
public:
	void label_dfs();

public:
	/*
	 * Commented out on Dec 21, 2010
	 vector<vector<Interval> > label_multiple_interval();
	 void compute_successors(vector<EdgeList>& succ);
	 void compute_predecessors(vector<EdgeList>& pred);
	 */
	//                                    vid  pred(vid)             vid  succ(vid)
	void uncovered_transitive_closure(map<int, PredList>& upred, map<int,
			SuccList>& usucc, map<int, SuccList>& gsucc);

private:
	/*
	 GridHop find_grid_hop2(DTree& tree, NTEList& NTE, int r, vector<bool>& visited,
	 map<int, PredList>& pred, map<int, SuccList>& succ);
	 GridHop find_grid_hop(map<int, PredList>& pred, map<int, SuccList>& succ);
	 */
	// usucc: uncovered successors; upred: uncovered predecessors
	// gsucc: successors covered by G[~LNTE]; gpred: predecessors covered by G[~LNTE]

	double hop_density_1(int u, int v, map<int, PredList>& pred, map<int,
			SuccList>& succ);
	double hop_density_2(int u, int v, map<int, PredList>& pred, map<int,
			SuccList>& succ);
	double hop_density_3(int u, int v, map<int, PredList>& pred, map<int,
			SuccList>& succ, map<int, PredList>& gpred,
			map<int, SuccList>& gsucc);
	int hop_density_4(int u, int v, map<int, PredList>& pred,
			map<int, SuccList>& succ, map<int, PredList>& gpred, map<int,
					SuccList>& gsucc, int& csize);
	double hop_density_5(int u, int v, map<int, PredList>& pred, map<int,
			SuccList>& succ, int selfu, int selfv);

	GridHop find_grid_hop_1(HOPQUEUE& hops);
	GridHop find_grid_hop_2(map<int, PredList>& upred,
			map<int, SuccList>& usucc, map<int, PredList>& gpred, map<int,
					SuccList>& gsucc);
	GridHop find_grid_hop_3(map<int, PredList>& upred,
			map<int, SuccList>& usucc, map<int, SuccList>& gsucc);

	// for test
private:
	void print_succ(map<int, SuccList>& succ);
	void print_pred(map<int, PredList>& pred);

public:
	void label_grid_hop();
	void sortByDFLN();
public:
	void create_label();

public:
	void print_label(ostream& os); // for test

public:
	bool reach(int src, int trg);
	bool test_reach();
	void test_reach2(int src, int trg);
	bool test_reach(int src, int trg);
	void printNode(int a);

	//    bool lessPreN(const int& p1, const int& p2);
	/* Commented out on Dec 16, 2010
	 void compute_tcm();
	 */

public:
	// only for testing functionalties of TestReachability when programming
	void test();
	//    bool reach(int src, int trg);
	//    void test_reach();
	void uncovered_transitive_closure_evaluate(int& t, int& c);
	int index_size();
	DGraph& getGraph();
	int contourSize();
	int gsuccSize();
	int contourTopSize(map<int, hash_set<int> >& contour) ;
	void caculateTransitiveClosure();

	bool reach3(int src, int trg);

	int size();
	bool reach_bak(int src, int trg);
	bool reach_bak2(int src, int trg);
private:

	void reduceUncoveredPairs(map<int, SuccList>& usucc,
			map<int, PredList>& upred, vector<int>& srcToRemove,
			vector<int>& trgToRemove, int x, int y, int& reduced);

	bool reach2(int src, int trg);

	void GhopContour();
	void GhopContour2(int vid, map<int,
			hash_set<int> >& contour, map<int, hash_set<int> >& contour_top,map<int, hash_set<int> >& temp_gsucc);
	void inputCmd();

};

#endif // TESTREACHABILITY_H_INCLUDED
